package com.atguigu.structures.linkedlist;

import com.atguigu.structures.linkedlist.node.SingleNode;

import java.util.Stack;

/**
 * 单链表工具类 - 常见面试题
 * @author xr-8
 * @create 2020-10-03 22:15
 */
public class SingleLinkedListUtil {
    /**
     * 获取链表有效节点的个数
     * @param head
     */
    public static int getLength(SingleNode head) {
        if(head.next == null) { //空链表
            return 0;
        }
        int length = 0;
        //定义一个辅助的变量, 这里我们没有统计头节点
        SingleNode cur = head.next;
        while(cur != null) {
            length++;
            cur = cur.next; //遍历
        }
        return length;
    }

    /**
     * 获取链表倒数第k个节点
     * 1. 先把链表从头到尾遍历，得到链表的总的长度 getLength
     * 2. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
     * 3. 如果找到了，则返回该节点，否则返回nulll
     * @param head
     * @param index 倒数第k个节点
     * @return
     */
    public static SingleNode getK(SingleNode head, int index) {
        //判断如果链表为空，返回null
        if(head.next == null) {
            return null;//没有找到
        }
        //第一个遍历得到链表的长度(节点个数)
        int size = getLength(head);
        //第二次遍历  size-index 位置，就是我们倒数的第K个节点
        //先做一个index的校验
        if(index <=0 || index > size) {
            return null;
        }
        //定义给辅助变量， for 循环定位到倒数的index
        SingleNode cur = head.next; //3 // 3 - 1 = 2
        for(int i =0; i< size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 反转单链表
     * @param head
     */
    public static void reverseList (SingleNode head) {
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if(head.next == null || head.next.next == null) {
            return ;
        }
        SingleNode cur = head.next; //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
        SingleNode next = null; //指向当前节点[cur]的下一个节点
        SingleNode reverseHead = new SingleNode(-1,"","");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
        while (cur != null) {
            next = cur.next; //先暂时保存当前节点的下一个节点，因为后面需要使用
            cur.next = reverseHead.next; //将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur; //将cur连接到新的链表上
            cur = next; //指针cur后移
        }
        //将head.next 指向 reverseHead.next , 实现单链表的反转
        head.next = reverseHead.next;
    }

    /**
     * 逆序打印
     * 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
     * @param head
     */
    public static void reversePrint(SingleNode head) {
        if(head.next == null) {
            return;//空链表，不能打印
        }
        //创建要给一个栈，将各个节点压入栈
        Stack<SingleNode> stack = new Stack<SingleNode>();
        SingleNode cur = head.next;
        //将链表的所有节点压入栈
        while(cur != null) {
            stack.push(cur);
            cur = cur.next; //cur后移，这样就可以压入下一个节点
        }
        //将栈中的节点进行打印,pop 出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop()); //stack的特点是先进后出
        }
    }

    /**
     * 合并两个有序链表
     * @param dist 源链表
     * @param src 源链表
     */
    public static SingleLinkedList mergeLinkedList(SingleLinkedList dist, SingleLinkedList src) {
        if (dist == null || dist.getHead().next == null) {
            return src;
        }
        if (src == null || src.getHead().next == null) {
            return dist;
        }
        SingleNode cur = src.getHead().next;
        while (cur != null) { // 需要将cur单独拆出来，即next也要拆掉
            SingleNode temp = cur;
            src.getHead().next = cur.next;
            dist.addByOrder(temp);
            cur = src.getHead().next;
        }
        return dist;
    }
}